(module Diff-tree
  (lib "eopl.ss" "eopl")
  (require "drscheme-init.scm")     
  (provide value-of zero diff-tree-plus one-tree diff)

;;Diff-tree::==(one) | (diff Diff-tree Diff-tree)
;;
;;Diff-tree ::= (one)
;;          ::= (diff Diff-tree Diff-tree)

(define-datatype Diff-tree Diff-tree?
  (one-tree (lst list?))   
  (diff     
   (l Diff-tree?)
   (r Diff-tree?))
  )


;;Example sets for this definition
;;
(define t1 (one-tree '(one)))
(define t2 (diff t1 t1))

;;  2.3.1 : Show that every number has infinite representations : 
;;[1] = (one)
;;[1] = (diff (one) (diff (one) (one)))
;;[-1] =(diff (diff (one) (one)) (one))
;;[2] = (diff (diff (one) (diff (one) (one)))      (diff (diff (one) (one)) (one))) 
;;             ***********[1] ***************minus (******* -1 ***************)
;;This can be extended to any integer
;;
;;Also we can get to any number by adding and subtracting different integers and thus
;;We can have infinite representations of the same number
;; by adding or  subtracting the (zero). (zero) is a function defined below that 
;; can be added  any number of times  to a diff tree 
;; making no difference in the resul 
;;thus  we can say that any number  can have infinite re[resentation. 
;;programtically ,  if we use the "diff-tree-plus" function created below ..
  ;; we can say for any given tree dt 
  ;; (diff-tree-plus dt (zero)) = dt
;;
;;
  
  
;;zero: 1 - (1)
;;zero ::= (diff (one) (one))
;;zero: With (one) being the  least possible  number here ,  
;;       we can define zero by 
;;       subtracting one from one. 
(define zero
  (lambda ()
    (diff
     (one-tree '(one))
     (one-tree '(one))
     )
    )
  )

;;define (one) 
;; 0 - ( -1)

;;defining one
(define one (one-tree '(one)))
;;define minus-1
(define minus-1
  (lambda ()
    (diff
     (zero)
     (one-tree '(one))
     )
    )
  )

;;value-fof: Diff-tree ==> number
;;usage: (value-of dt)
;;purpose 
(define value-of
  (lambda (dt)
    (cases Diff-tree dt
      (one-tree (lst) 1)
      (diff (l r)
            (- (value-of l) (value-of r))
            )
      )
    )
  )

;;is-zero?: Diff-Tree ==> boolean
;;usage: (is-zero? dt)
;;Purpose: This Procedure takes a Diff-tree as input and 
;;         gives a #t if the Diff-Tree represents a 0 
;;         and a #f if the tree represents a non zero number
(define is-zero? 
  (lambda (dt)
  (if (= (value-of dt) 0) 
      #t
      #f
      )
    )
  )

;;predecessor: Diff-tree ==> Diff-tree 
;;usage:(predecessor dt)
;;purpose: Given a diff-tree ,  this procedure produces the value that
;;         is the  predecessor or  one  lesser than the given value. 
(define predecessor
  (lambda (dt)
       (diff dt (one-tree '(one)))
    )
  )

;;successor: Diff-tree ==> Diff-tree 
;;usage:(successor dt)
;;purpose: Given a diff-tree ,  this procedure produces the value that
;;         is the  successor or  one  greater than the given value. 
(define successor
  (lambda (dt)
       (diff dt (minus-1))
    )
  )


;;diff-tree-plus: Diff-tree * Diff-tree ==> Diff-tree
;;usage:(diff-tree-plus dt)
;;purpose: Given two  Diff-tree(s), this procedure produces another Diff-tree
;;         that represents the sum of the given two given Diff-tree(s)
;;;;;;;;;;;;;;;;;;    X + Y  == X - ( 0 - Y)  ;;;;;;;;;;;;;;;;;;;;
;; Since for any Given Tree ,  all we are doing is creating 
;; 2 levels  of nested Diff-trees this  is always using constant time 
;; satisfying the  requirement of the  problem 
;;examples: 
;; (value-of (diff-tree-plus (zero) (zero))) ==> 0
;; (value-of  (diff-tree-plus (one-tree '(one)) (zero))) --> 1
(define diff-tree-plus
  (lambda (dt1 dt2)
    (diff dt1 (diff (zero) dt2))
    )
  )
  
)  